/**
 * @filename AVLTree.h
 * @brief AVLTree
 * @author Sun Zehui <sunzehui18@outlook.com>
 * @version 1.0.0
 * @date 2021-11-24
 */
#ifndef __AVLTREEH__
#define __AVLTREEH__

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
using namespace std;

template<typename Comparable>
class AVLTree;

/**
 * @brief BST_sort 普通的二叉树排序，没有经过随即shuffle
 *
 * @tparam Comparable 可比较对象
 * @param _data 待排数据r
 */
template<typename Comparable>
void AVL_BST_sort(vector<Comparable> &_data){
	AVLTree<Comparable> tree;
	for(auto iter=_data.begin(); iter!=_data.end(); ++iter){
		tree.insert(*iter);
	}

	_data.clear();
	tree.inorder(_data);
}

/**
 * @brief Randomized_BST_sort 随机的二叉树排序
 *
 * @tparam Comparable 可比较对象
 * @param _data 待排数据
 */
template<typename Comparable>
void AVL_Randomized_BST_sort(std::vector<Comparable> &_data){
	shuffle(_data.begin(), _data.end(), default_random_engine(2));
	AVLTree<Comparable> tree;
	for(auto iter=_data.begin(); iter!=_data.end(); ++iter){
		tree.insert(*iter);
	}

	_data.clear();
	tree.inorder(_data);
}

template <typename Comparable>
class AVLTree{
public:
    AVLTree():root(nullptr){}
	~AVLTree()
	{
		makeEmpty();
	}
	/**
	 * @brief insert 封装方法
	 *
	 * @param x Comparable&
	 */
	virtual void insert(const Comparable& x){
		insert(x, root);
	}
	virtual void insert(Comparable&& x){
		insert(std::move(x), root);
	}

	virtual void makeEmpty(){
		makeEmpty(root);
	}

	/**
	 * @brief inorder 中序遍历覆盖Vector
	 *
	 * @param vec Vector<Comparable>
	 */
	virtual void inorder(vector<Comparable>& vec){
		inorder(root, vec);
	}

	virtual void preorder(vector<Comparable>& vec){
		preorder(root, vec);
	}

	virtual void postorder(vector<Comparable>& vec){
		preorder(root, vec);
	}

	bool contains(const Comparable& x) {
		if(contains(x,root)==nullptr)
			return false;
		return true;
	}

private:
    static const int ALLOWED_IMBALANCE = 1;

	struct AvlNode
	{
		Comparable element;
    	int height;
		AvlNode *left;
		AvlNode *right;
    	AvlNode(const Comparable & ele, AvlNode *lt, AvlNode *rt, int h=0)
        	:element(ele), left(lt), right(rt), height{h} {}
    	AvlNode(Comparable && ele, AvlNode *lt, AvlNode *rt, int h=0)
        	:element(ele), left(lt), right(rt), height{h} {}
	};

    AvlNode *root;

    /**
     * @brief height get height
     *
     * @param t node
     *
     * @return height int
     */
    int height(AvlNode * t) const
    {
        return t == nullptr ? -1 : t->height;
    }

    /**
     * @brief insert after insetion a balance will be needed
     *
     * @param x value
     * @param t node
     */
    void insert(const Comparable& x, AvlNode* & t)
    {
        if(t==nullptr)
            t = new AvlNode{x, nullptr, nullptr};
        else if (x<t->element)
            insert(x, t->left);
        else if (t->element<x)
            insert(x,t->right);

        balance(t);
    }

    /**
     * @brief contains same contains
     *
     * @param x
     * @param t
     *
     * @return 
     */
	AvlNode* contains(const Comparable& x, AvlNode *t){
		if( t == nullptr )
			return nullptr;
		else if( x < t->element )
			return contains( x, t->left );
		else if( t->element < x )
			return contains( x, t->right );
		else
			return t;
	}

	/**
	 * @brief balance Balance operation
	 *
	 * @param t node
	 */
    void balance(AvlNode* & t)
    {
        if(t==nullptr)
            return;
        
        if(height(t->left)-height(t->right)>ALLOWED_IMBALANCE)
            if(height(t->left->left)>=height(t->left->right))
                rotateWithLeftChild(t);
            else
                doubleWithLeftChild(t);
        else if(height(t->right) - height(t->left)>ALLOWED_IMBALANCE)
            if(height(t->right->right)>=height(t->right->left))
                rotateWithRightChild(t);
            else
                doubleWithRightChild(t);
        
        t->height = max(height(t->left), height(t->right)) +1;
    }

    /**
     * @brief rotateWithLeftChild 左单旋
     *
     * @param k2 node
     */
    void rotateWithLeftChild(AvlNode*& k2)
    {
        AvlNode *k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max(height(k2->left), height(k2->right))+1;
        k1->height = max(height(k1->left), k2->height)+1;
        k2 = k1;
    }

	void rotateWithRightChild(AvlNode*& k2)
	{
		AvlNode* k1 = k2->right;
		k2->right = k1->left;
		k1->left = k2;
		k2->height = max(height(k2->left), height(k2->right))+1;
		k1->height = max(height(k1->right), k2->height)+1;
		k2 = k1;
	}

	/**
	 * @brief doubleWithLeftChild 左双悬
	 *
	 * @param k3 node
	 */
    void doubleWithLeftChild(AvlNode*& k3)
    {
        rotateWithRightChild(k3->left);
        rotateWithLeftChild(k3);
    }

	void doubleWithRightChild(AvlNode*& k3)
	{
		rotateWithLeftChild(k3->right);
		rotateWithRightChild(k3);
	}

	void makeEmpty(AvlNode* & t){
		if(t!=nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}

	/**
	 * @brief inorder 中序遍历的递归表达
	 *
	 * @param t 节点
	 * @param vec Vector<Comparable>
	 */
	void inorder(AvlNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			inorder(t->left, vec);
			vec.push_back(t->element);
			inorder(t->right, vec);
		}
	}

	void preorder(AvlNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			vec.push_back(t->element);
			inorder(t->left, vec);
			inorder(t->right, vec);
		}
	}

	void postorder(AvlNode *t, vector<Comparable>& vec){
		if(t == nullptr)
			return;
		else{
			inorder(t->left, vec);
			inorder(t->right, vec);
			vec.push_back(t->element);
		}
	}
};

#endif
